package Graph;

import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingDeque;


public abstract class Graph {
    protected final static int INFINITY = Integer.MAX_VALUE;
    protected final static int BFS = 0;
    protected final static int DFS = 1;

    protected GraphKind kind;
    protected Object[] vexs;  // 顶点集合(顺序存储)
    protected ArrayList<Vertex> vertexList; // 顶点集合(链式存储)
    protected int[][] arcs;   // 邻接关系集合

    protected int vexNum; // 顶点数量
    protected int arcNum; // 边(弧)数量

    protected boolean[] visited; // 是否已被遍历的标志位(长度等于顶点数量)
    protected List<Object> bfsList; // bfs访问序列
    protected List<Object> dfsList; // dfs访问序列
    protected Queue<Integer> queue = new LinkedBlockingDeque<>(); // dfs访问辅助队列


    public Graph() {

    }

    public abstract int getVexNum();

    public abstract int getArcNum();

    public abstract Object getVex(int v);

    public abstract int locateVex(Object vex);

    public abstract int firstAdjVex(int v) throws Exception;

    public abstract int nextAdjVex(int v, int w) throws Exception;

    public Graph(GraphKind kind, int arcNum, Object[] vexs, int[][] arcs) {
        this.arcNum = arcNum;
        this.vexNum = vexs.length;
        this.arcs = new int[vexNum][vexNum];
        this.vexs = new Object[vexs.length];   // 初始化顶点数组的值
    }

    public void traverseDFS(int startVex) {
        if (startVex < 0 || startVex >= vexNum) {
            System.out.println("不存在第" + startVex + "个顶点");
            return;
        }

        dfsList = new ArrayList<>();
        // 对访问标志位数组进行初始化
        visited = new boolean[this.vexNum];
        System.out.println("该城市是："+ getVex(startVex));
        System.out.println("该城市到其他城市的网线线路的权值分别为：");
        for (int i = 0; i < visited.length; i++) {
            visited[i] = false;
        }

        dfs(startVex);


    }

    protected abstract void dfs(int v);

    public void traverseBFS(int startVex) {
        if (startVex < 0 || startVex >= vexNum) {
            System.out.println("不存在第" + startVex + "个顶点");
            return;
        }

        bfsList = new ArrayList();
        // 对访问标志位数组进行初始化
        visited = new boolean[this.vexNum];
        for (int i = 0; i < vexNum; i++) {
            visited[i] = false;
        }

        // 从第一个顶点出发找它的所有邻接点
        bfs(startVex);


    }


    protected abstract void bfs(int v);


    public abstract void showVexs();


    public abstract void showArcs();
}